package leetcode.LinkedList;

/**
 * @author MaoLin Wang
 * @date 2020/2/1120:25
 */
public class _234IsPalindrome {


    public static ListNode findLastHlf(ListNode head){
        ListNode slow=head;
        ListNode fast=head;

        while (fast.next!=null && fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }

    /**
     *  通过快慢指针找到后半部分节点，反转之
     *   分别比较前半部分链表和反转后的后半部分链表
     * @param head
     * @return
     */
    public static boolean isPalindrome2(ListNode head) {
        if (head==null){
            return false;
        }
        if (head.next==null){
            return true;
        }
        ListNode fast=head;
        ListNode slow=head;
        while (fast.next!=null && fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode reverse = _206ReverseList.reverseList3(slow.next);
        ListNode cur=head;
        while (cur!=null && reverse!=null){
            if (cur.val!=reverse.val){
                return false;
            }
            cur=cur.next;
            reverse=reverse.next;
        }
        return true;

    }
    public static void main(String[] args) {
        ListNode l1=new ListNode(1);
        l1.next=new ListNode(2);
        l1.next.next=new ListNode(3);
        l1.next.next.next=new ListNode(2);
        l1.next.next.next.next=new ListNode(1);

        boolean palindrome = isPalindrome2(l1);
        System.out.println(palindrome);


    }
}
